package com.shm.leetcode;

/**
 * 88. 合并两个有序数组
 * 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
 *
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
 * 输出：[1,2,2,3,5,6]
 * 示例 2：
 *
 * 输入：nums1 = [1], m = 1, nums2 = [], n = 0
 * 输出：[1]
 *
 *
 * 提示：
 *
 * nums1.length == m + n
 * nums2.length == n
 * 0 <= m, n <= 200
 * 1 <= m + n <= 200
 * -109 <= nums1[i], nums2[i] <= 109
 * @author SHM
 */
public class Merge {
    /**
     * 方法二 : 双指针 / 从前往后
     * 直觉
     *
     * 一般而言，对于有序数组可以通过 双指针法 达到O(n + m)O(n+m)的时间复杂度。
     *
     * 最直接的算法实现是将指针p1 置为 nums1的开头， p2为 nums2的开头，在每一步将最小值放入输出数组中。
     *
     * 由于 nums1 是用于输出的数组，需要将nums1中的前m个元素放在其他地方，也就需要 O(m)O(m) 的空间复杂度。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(nums2==null||n==0){
            return;
        }
        int i= 0,j=0;
        int len = nums1.length;
        int[] ans = new int[len];
        for(int k=0;k<len;k++){
            if(i<m&&(j>=n||nums1[i]<=nums2[j])){
                ans[k]=nums1[i];
                i++;
            }else if(j<n){
                ans[k]=nums2[j];
                j++;
            }
        }

        for(int k=0;k<len;k++){
            nums1[k] = ans[k];
        }
    }

    /**
     * 方法三 : 双指针 / 从后往前
     * 直觉
     *
     * 方法二已经取得了最优的时间复杂度O(n + m)O(n+m)，但需要使用额外空间。这是由于在从头改变nums1的值时，需要把nums1中的元素存放在其他位置。
     *
     * 如果我们从结尾开始改写 nums1 的值又会如何呢？这里没有信息，因此不需要额外空间。
     *
     * 这里的指针 p 用于追踪添加元素的位置。
     * 复杂度分析
     *
     * 时间复杂度：O(m+n)O(m+n)
     * 指针移动单调递减，最多移动 m+nm+n 次，因此时间复杂度为 O(m+n)O(m+n)。
     *
     * 空间复杂度：O(1)O(1)
     * 直接对数组 \textit{nums}_1nums
     * 1
     * ​
     *   原地修改，不需要额外空间。
     *
     * 作者：LeetCode
     * 链接：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge_2(int[] nums1, int m, int[] nums2, int n) {
        if (nums2 == null || n == 0) {
            return;
        }
        int i = m-1, j = n-1;
        int len = nums1.length;
        for(int k=len-1;k>=0;k--){
            if(i>=0&&(j<0||nums1[i]>nums2[j])){
                nums1[k] = nums1[i];
                i--;
            }else if(j>=0){
                nums1[k] = nums2[j];
                j--;
            }
        }
    }

    public void merge_3(int[] nums1, int m, int[] nums2, int n) {
        if(n==0){
            return;
        }

        int i=m-1,j=n-1,k=nums1.length-1;
        while(k>=0){
            if(i>=0&&j>=0){
                if(nums1[i]>nums2[j]){
                    nums1[k] = nums1[i];
                    i--;
                }else{
                    nums1[k] = nums2[j];
                    j--;
                }
            }else {
                if(j>=0){
                    nums1[k]=nums2[j];
                    j--;
                }
            }
            k--;
        }
    }
}
